home *** CD-ROM | disk | FTP | other *** search
/ Informática Multimedia 1995 April / Informatica Multimedia CD - Epimundo.iso / DOS / FILE_CHG / KSORT12.ZIP / KSORT.C < prev    next >
Encoding:
C/C++ Source or Header  |  1991-06-06  |  9.6 KB  |  384 lines
  1. /*
  2.  * ksort.c
  3.  * Copyright (c) 1989 Josh Greifer
  4.  * sort big text files that DOS sort.com can't cope with
  5.  * over 30 times faster than DOS sort.com
  6.  * try it on huge files!
  7.  *
  8.  * compile with Microsoft C V. 6.0 like this:
  9.  * (note that the Compact Model is used)
  10.  *    cl /AC /Ox ksort.c
  11.  * or use the makefile provided:
  12.  *    make ksort.mak
  13.  */
  14. #include <stdio.h>
  15. #include <stdlib.h>
  16. #include <string.h>
  17. #include <malloc.h>
  18. #include <ctype.h>
  19.  
  20. #define MAXLINELEN 1024
  21. #define DEFARRAYSIZE 16000
  22. #define MAXARRAYSIZE 64000
  23. #define MAXFILES    FOPEN_MAX-5
  24. #define EMBUFSIZE   4096
  25. #define QSSSIZE     1024
  26.  
  27. #define DUMMY1ST    ((char *)-1)
  28. #define DUMMYLAST   ((char *)-2)
  29.  
  30. FILE *inf, *ouf;
  31. int _near offset = 1;
  32. int _near skipspace;
  33. int _near rename_;
  34. int _near verbose;
  35. unsigned int _near asize;
  36. unsigned int _near insert;
  37.  
  38. char *infname, *oufname;
  39.  
  40. typedef struct {
  41.     FILE *fp;        /* file pointer */
  42.     char *fn;        /* file name    */
  43.     char *buf;        /* buffer    */
  44. } FS;
  45.  
  46. FS _near tmpftab[MAXFILES];
  47.  
  48. int _near tmpfiles;   /* number of temp files created */
  49.  
  50. void parseargs(int, char **);
  51. void error(char *, char *);
  52. int revcmpi(char *, char *);
  53. int revcmp(char *, char *);
  54. void merge(void);
  55. void spool_to_tmpfile( char * _huge *array );
  56.  
  57. void    ksort( char * _huge *, unsigned int, int (*)( char *, char *));
  58. void    isort( char * _huge *, unsigned int, int (*)( char *, char *));
  59.  
  60. int (*cmpfns[])(char *, char *) = { stricmp, strcmp };
  61. int (*revcmpfns[])(char *, char *) = { revcmpi, revcmp };
  62. int (**cmpfn)(char *, char *) = cmpfns;
  63.  
  64. void getnextline( FS *f );
  65.  
  66. unsigned int _near * _near qs;             /* quicksort stack bottom */
  67. char _near *qsss = "QuickSort internal stack";
  68. char *emergency;                /* freed when malloc() fails */
  69. char * _huge *array;
  70.  
  71. main(int argc, char **argv)
  72. {
  73.     char buf[MAXLINELEN];
  74.     char *p = buf;
  75.     register unsigned int i=0, j=0;
  76.     long l = 0L;
  77.  
  78.     tmpftab[0].fp = (FILE *)1; /* pseudo file */
  79.  
  80.     emergency = malloc(EMBUFSIZE);
  81.     parseargs(argc, argv);
  82.  
  83.     if ((array = (char *_huge *)halloc((asize+1),sizeof(char *))) == NULL)
  84.     error("Default buffer too big - use /B to specify size", NULL);
  85.  
  86.    if ((qs = (int _near *)_nmalloc(QSSSIZE*sizeof(int)))==0)
  87.     error("Can't allocate %s\n", qsss);
  88. loop:
  89.     if (verbose) fprintf(stderr, "\nReading file...");
  90.     if (verbose == 2) fprintf(stderr, "\nReading line %ld", l);
  91.  
  92.     for (i = 1; i < asize && fgets(buf, MAXLINELEN, inf); i++, l++) {
  93.     if (verbose == 2) fprintf(stderr, "\rReading line %ld", l);
  94.     if (skipspace) for (p = buf; isspace(*p); p++);
  95.     if ((array[i] = strdup(p)) == NULL) {
  96.         free(emergency);
  97.         emergency = NULL;
  98.         array[i++] = strdup(p);
  99.         break;
  100.     }
  101.     }
  102.     if (verbose) fprintf(stderr, "\nSorting...");
  103.     array[0] = DUMMY1ST;
  104.     array[i] = DUMMYLAST;
  105.  
  106.     ksort(array, i-1, *cmpfn);
  107.  
  108.     if (i == asize || !emergency) {
  109.  
  110.     spool_to_tmpfile(array);
  111.  
  112.     if (!emergency) emergency = malloc(EMBUFSIZE);
  113.     goto loop;
  114.     }
  115.     else {
  116.     if (tmpfiles) merge();
  117.     else {
  118.         if (verbose) fprintf(stderr, "\nOutputting sorted file...");
  119.         for (j = 1; j < i; j++)
  120.         fputs(array[j], ouf);
  121.     }
  122.     }
  123.     fclose(inf);
  124.     fclose(ouf);
  125.     if (rename_) {
  126.     unlink(infname);
  127.     rename(oufname, infname);
  128.     }
  129.     return 0;
  130. }
  131.  
  132. void    spool_to_tmpfile( char * _huge *array )
  133. {
  134.     char buf[FILENAME_MAX];
  135.  
  136.     FS *tmpfs = &tmpftab[++tmpfiles];
  137.  
  138.     unsigned int j;
  139.  
  140.     if (verbose)
  141.     fprintf(stderr,"\nWriting temp file %d...",tmpfiles);
  142.  
  143.     sprintf(buf, "SRTQ_%d.$$$", tmpfiles);
  144.     tmpfs->fn = strdup(buf);
  145.     if ((tmpfs->fp = fopen(tmpfs->fn, "w+"))==0)
  146.     error("Error creating temp file %s", tmpfs->fn);
  147.     if ((tmpfs->buf = (char *)malloc(MAXLINELEN)) == 0)
  148.     error("Can't allocate temp file buffer.\n", NULL);
  149.  
  150.     for (j = 1; array[j] != DUMMYLAST; j++) {
  151.     fputs(array[j], tmpfs->fp);
  152.     if (array[j] != DUMMY1ST) free(array[j]);
  153.     }
  154. }
  155.  
  156. void error(char *message, char *var)
  157. {
  158.     if (emergency) free(emergency);
  159.     if (*message != '\n') fprintf(stderr, "\nFatal error:");
  160.     fprintf(stderr, message, var);
  161.     exit(1);
  162. }
  163.  
  164.  
  165. void merge()
  166. {
  167.     register FS *i,*j;
  168.     FS *maxtmpf = &tmpftab[tmpfiles+1];
  169.  
  170.     if (verbose) fprintf(stderr, "\nMerging %d temp file%c..", tmpfiles,
  171.     tmpfiles > 1 ? 's' : '.');
  172.  
  173.     for (i = tmpftab+1; i < maxtmpf; i++) {
  174.     fflush(i->fp);
  175.     fseek(i->fp,0L,SEEK_SET);
  176.     }
  177.  
  178.     for (i = tmpftab; i < maxtmpf; i++)
  179.     if (i->fp)          /* tmpftab[m].fp set to NULL after EOF */
  180.         getnextline(i);
  181.     if (verbose) fprintf(stderr, "\nOutputting sorted file...");
  182.     for (;;) {
  183.     for (j = tmpftab; !j->fp; j++)       /* find a buffer */
  184.         if (j >= maxtmpf) return;       /* EOF on all temp files */
  185.     for (i = j+1; i < maxtmpf; i++)    /* compare all other bufs with j */
  186.         if (i->fp)
  187.         if ((*cmpfn)(j->buf+offset, i->buf+offset) > 0)
  188.             j = i;            /* j := next buffer to be output */
  189.     fputs(j->buf, ouf);
  190.     getnextline(j);
  191.     }
  192. }
  193.  
  194. void getnextline( register FS *f )
  195. {
  196.     static int pos;
  197.     if (f == tmpftab) {     /* pseudo-file -- data is in array[] */
  198.     if ((f->buf = array[++pos]) == DUMMYLAST) {
  199.         f->fp = NULL;
  200.         f->buf = "";
  201.     }
  202.     }
  203.     else if (fgets(f->buf, MAXLINELEN, f->fp)==NULL) {
  204.     fclose(f->fp);
  205.     f->fp = NULL;
  206.     unlink(f->fn);
  207.     }
  208. }
  209.  
  210. #define CLEARSTACK() stackptr = qs; stackend = stackptr+QSSSIZE-2
  211. #define STACKEMPTY() (stackptr == qs)
  212. #define PUSH(a,b)    if (stackptr >= stackend) error("%v overflow", qsss); \
  213.     else *stackptr++ = (a); *stackptr++ = (b)
  214. #define POP(a,b)     (b) = *--stackptr; (a) = *--stackptr
  215.  
  216. #define SWAP(Km, Kn)        temp = (Km); (Km) = (Kn); (Kn) = temp
  217.  
  218. #define LESSTHAN(Km, Kn)    ((Km) == DUMMY1ST ? 1 : \
  219.     (Kn) == DUMMY1ST ? 0 : (Km) == DUMMYLAST ? 0 : \
  220.     (Kn) == DUMMYLAST ? 1 : (*comp)( (Km)+offset, (Kn)+offset) < 0)
  221.  
  222. #define GREATERTHAN(Km, Kn)    ((Km) == DUMMY1ST ? 0 : \
  223.     (Kn) == DUMMY1ST ? 1 : (Km) == DUMMYLAST ? 1 : \
  224.     (Kn) == DUMMYLAST ? 0 : (*comp)( (Km)+offset, (Kn)+offset) > 0)
  225.  
  226. void    ksort( char * _huge *v, unsigned int N, int (*comp)( char *, char *))
  227. {
  228.     unsigned int l, r, i, j;
  229.     char *temp;
  230.     unsigned int     _near *stackptr;
  231.     unsigned int     _near *stackend;
  232.     unsigned int     M = insert;
  233.     unsigned int    p = 0;
  234.  
  235. /* Q1: Initialize   */
  236.     if (N <= M) goto Q9;
  237.     if (verbose) fprintf(stderr, "\nQuickSort...%c",
  238.                      verbose == 2 ? '\n' : '\0');
  239.     CLEARSTACK();
  240.     l = 1; r = N;
  241.  
  242. Q2: /* Begin new stage */
  243.     if (verbose == 2) fprintf(stderr, "\r%u partitions processed",++p);
  244.     i = l; j = r+1;
  245.  
  246. Q3: /* Compare Ki : K */
  247.     ++i;
  248.     if (LESSTHAN(v[i], v[l]))
  249.     goto Q3;
  250.  
  251. Q4: /* Compare K : Kj */
  252.     --j;
  253.     if (LESSTHAN(v[l], v[j]))
  254.     goto Q4;
  255.  
  256. /* Q5: Test i : j */
  257.     if (j <= i) {
  258.     SWAP(v[l], v[j]);
  259.     goto Q7;
  260.     }
  261.  
  262. /* Q6: Exchange */
  263.     SWAP(v[i], v[j]);
  264.     goto Q3;
  265.  
  266. Q7: /* Put on stack */
  267.     if ((r-j >= j-l) && (j-l > M) ) {
  268.     PUSH(j+1, r);
  269.     r = j-1;
  270.     goto Q2;
  271.     }
  272.     if ((j-l > r-j) && (r-j > M)) {
  273.     PUSH(l, j-1);
  274.     l = j+1;
  275.     goto Q2;
  276.     }
  277.     if ((r-j > M) && (M >= j-l)) {
  278.     l = j+1;
  279.     goto Q2;
  280.     }
  281.     if ((j-l > M) && (M >= r-j) ) {
  282.     r = j-1;
  283.     goto Q2;
  284.     }
  285.  
  286. /* Q8: take off stack */
  287.     if (!STACKEMPTY()) {
  288.     POP(l, r);
  289.     goto Q2;
  290.     }
  291. Q9: /* Straight insertion sort */
  292.     if (M > 1) isort(v, N, comp);
  293. }
  294.  
  295. void    isort( char * _huge *v, unsigned int N, int (*comp)( char *, char *))
  296. {
  297.     unsigned int i, j;
  298.     char *K;
  299.     if (verbose) fprintf(stderr, "\nInsertion sort...%c",
  300.                      verbose == 2 ? '\n' : '\0');
  301.     for (j = 2; j <= N; j++) {
  302.     if (verbose == 2) fprintf(stderr, "\r%u records processed",j-1);
  303.     if (GREATERTHAN(v[j-1], v[j])) {
  304.         K = v[j];
  305.         i = j-1;
  306.         do {
  307.         v[i+1] = v[i];
  308.         i--;
  309.         } while (GREATERTHAN(v[i], K));
  310.         v[i+1] = K;
  311.     }
  312.     }
  313. }
  314.  
  315. int revcmpi( register char *a1, register char *a2)
  316. {
  317.     return strcmpi(a2, a1);
  318. }
  319.  
  320. int revcmp( register char *a1, register char *a2)
  321. {
  322.     return strcmp(a2, a1);
  323. }
  324.  
  325. void parseargs(int argc, char **argv)
  326. {
  327.     static char usage[] = "\n\
  328.     *** Ksort version 1.03 Copyright (c) Josh Greifer 1991 *** \n\
  329. Usage: ksort [/R] [/+<n>] [/N] [/S] [/V|v] [/B<n>] [/I<n>] [infile] [outfile]\n\
  330.        options: R      - reverse sort\n\
  331.         +<column> - start sort at column <n>\n\
  332.         N      - Don't ignore case\n\
  333.         S      - Skip and trim leading white space\n\
  334.         v      - verbose -- screen messages\n\
  335.         V      - Very verbose -- more screen messages\n\
  336.         B<n>      - Buffer size (number of lines) -- max %u\n\
  337.         I<n>      - Use Insertion Sort if fewer than <n> lines";
  338.     register char *c;
  339.     while (--argc) {
  340.     c = *++argv;
  341.     if (*c == '/')
  342.         switch (*++c) {
  343.         case 's':
  344.         case 'S':   skipspace++;          break;
  345.         case 'v':   verbose=1;            break;
  346.         case 'V':   verbose=2;            break;
  347.         case 'r':
  348.         case 'R':   cmpfn = revcmpfns;    break;
  349.         case 'n':
  350.         case 'N':   cmpfn++;              break;
  351.         case '+':   offset = atoi(++c); break;
  352.         case 'b':
  353.         case 'B':   asize =  atoi(++c);  break;
  354.         case 'i':
  355.         case 'I':   insert =  atoi(++c);  break;
  356.         default:    error(usage, (char *)MAXARRAYSIZE);
  357.         }
  358.     else if (!inf) {
  359.         infname = c;
  360.         if ((inf = fopen(infname, "r")) == NULL)
  361.         error("\nCan't open input file",infname);
  362.     }
  363.     else if (!ouf) {
  364.         oufname = c;
  365.         if ((ouf = fopen(oufname, "w")) == NULL)
  366.         error("\nCan't open output file",oufname);
  367.     }
  368.     else error(usage, NULL);
  369.     }
  370.     if (!ouf)
  371.     if (inf) {
  372.         ouf = fopen(oufname = strdup(tmpnam(NULL)), "w");
  373.         rename_ = 1;
  374.     } else {
  375.         inf = stdin;
  376.         ouf = stdout;
  377.     }
  378.  
  379.     offset--;
  380.     if (asize <= 1) asize = DEFARRAYSIZE;
  381.     if (insert <= 1) insert = 1;
  382.     if (insert >= asize) insert = asize;
  383. }
  384.